1. Field of the Invention
This invention relates to a method and apparatus for establishing an authenticated shared secret between a pair of users and, more particularly, to a method for generating a multiplicity of authenticated keys from a single statically generated, authenticated shared secret value.
2. Description of the Related Art
W. Diffie and M. E. Hellman describe, at page 649 of "New Directions in Cryptography", IEEE Transactions on Information Theory, vol. IT-22, no. 6, November 1976, pp. 644-654, as well as in U.S. Pat. No. 4,200,770, a protocol whereby a pair of conversers may establish a cryptographic key over an insecure communications channel subject to eavesdropping.
In accordance with the general form of the Diffie-Hellman key agreement protocol, each user generates a secret value X, which he keeps to himself, and from this generates a public value Y using a transformation that is infeasible to invert. One such transformation is EQU Y=g.sup.X mod p, (1)
where p is a large prime modulus and g is a generator over the Galois field GF(p). Regenerating X from Y generated in this manner amounts to determining the discrete logarithm of Y, which is considered to be a mathematically intractable problem. Each user transmits its own public value Y to the other user over a communications channel.
Each user then generates, from its own secret value X and the public value Y transmitted to it from the other user, a shared secret value Z that is infeasible to generate solely from the public values Y transmitted over the communications channel. Continuing the above example, one such transformation is EQU Z=Y.sup.X mod p, (2)
where p and g are defined as before.
Finally, one or more keys are derived by extracting bits from the shared secret value Z. Thus, to generate a series of n-bit keys, the most significant (i.e., leftmost) n bits of Z may be used to form a first key, the next most significant n bits of Z may be used to form a second key, and so on. (Alternatively, the extraction process may proceed from right to left.)
Since, by hypothesis, the transformation Y(X) is infeasible to invert, an eavesdropper on the communications channel cannot recover either of the secret values X from the public values Y transmitted over the channel. Further, since the shared secret value Z is infeasible to generate solely from the public values Y, an eavesdropper cannot generate Z (and hence the keys) by some other means, not using either of the secret values X.
Although the above protocol allows two parties to establish a private key between themselves over an insecure channel, it has some deficiencies. Directly taking portions of Z for a key has risks because of the possible presence of bias. For example, the high-order bit of Z tends to 0 for certain choices of p, as Z is the result of a modulo operation. Additionally, Z may have some structure that could be exploited by an attacker. Even if these weaknesses existed only for "bad" rare combinations of public values, they would still be undesirable.
Additionally, only a relatively small number of keys can be generated from a single exchange of public values Y, depending on the length of Z relative to the keys.
Finally, there is the problem of authentication, that is, how user A can be confident that he is communicating with user B and not, say, user C. There is nothing in the basic scheme that authenticates a public value Y as originating with a particular party. Thus, user A, believing that he has established a key with user B, may in fact have established the key with an impostor C.
Thus, some problems with the existing Diffie-Hellman protocol include (1) how to extract bits for a symmetric key from Z; (2) how to create a multiplicity symmetric keys; and (3) how to authenticate a key generated using the protocol.